ИМЯ¶

btree - метод доступа к базе данных двоичного дерева

ОБЗОР¶

#include <sys/types.h>
#include <db.h>

ОПИСАНИЕ¶

Примечание: В этой странице описаны интерфейсы, предоставляемые glibc до версии 2.1. Начиная с версии 2.2, glibc больше не поддерживает эти интерфейсы. Вероятно, вы ищите API, предоставляемое библиотекой libdb.

Функция dbopen(3) — это библиотечный интерфейс к файлам баз данных. Один из поддерживаемых форматов файлов — btree. Общее описание методов доступа к базам данных находится в dbopen(3). Эта справочная страница содержит только информацию, относящуюся к btree.

btree — это отсортированная, сбалансированная древовидная структура данных, содержащая связанные пары типа «ключ/данные».

Структура данных, с помощью которой к btree обращается dbopen(3), задана в <db.h> следующим образом:

typedef struct {


    unsigned long flags;


    unsigned int  cachesize;


    int           maxkeypage;


    int           minkeypage;


    unsigned int  psize;


    int         (*compare)(const DBT *key1, const DBT *key2);


    size_t      (*prefix)(const DBT *key1, const DBT *key2);


    int           lorder;
} BTREEINFO;

Элементы этой структуры имеют следующее назначение:

flags

Этот элемент определяется как логическое ИЛИ из следующих значений:

cachesize

Рекомендуемый максимальный размер (в байтах) для кэша в памяти. Этот элемент носит только рекомендательный характер, и при попытке доступа к данным может выделиться большее количество памяти. В последствии при каждом поиске проверяется корневая страница дерева, кэшируются наиболее часто используемые страницы, что уменьшает время, необходимое для доступа к данным. В дополнение к этому, физическая запись на диск откладывается настолько, насколько это возможно, что значительно уменьшает количество операций ввода/вывода. Очевидно, использование кэша увеличивает (но только увеличивает) вероятность повреждения или потери данных при падении системы при имеющихся изменённых данных. Если cachesize равно 0 (т. е., размер не указан), то используется размер кэша по умолчанию.

maxkeypage

Максимальное количество ключей, которые могут храниться на одной странице. В настоящее время данная возможность не реализована.

minkeypage

Минимальное количество ключей, которые могут храниться на одной странице. Эта величина используется для определения количества ключей, которые были сохранены при переполнении страницы. Т. е., если ключ или данные длиннее, чем pagesize, поделённый на величину minkeypage, они будут сохранены на отдельной странице. Если minkeypage равно 0 (минимальное количество ключей не определено), то величина принимается равной 2.

psize

Размер (в байтах) страницы, используемой для узлов дерева. Минимальный размер страницы — 512 байтов, максимальный — 64 килобайта. Если psize равно 0 (размер страницы не указан), то размер страницы получается равным размеру одного блока текущей системы ввода/вывода.

compare

Это функция сравнения ключей. Она возвращает целое значение, меньшее нуля, равное нулю или большее нуля, если первый аргумент соответственно меньше, равен или больше второго аргумента. При каждом открытии дерева для сравнения должна быть использована одинаковая функция. Если compare указывает на NULL (функция сравнения не определена), то ключи сравниваются лексически, т. е., короткие ключи меньше, чем длинные.

prefix

Это функция сравнения префиксов. Данная функция, если она определена, должна возвращать количество байтов во втором аргументе; это необходимо для того, чтобы определить, что данный аргумент больше, чем первый. Если аргументы равны, функция должна вернуть значение, равное длине ключа. Отметим, что эффективность этой функции в большой степени зависит от типа данных, но в некоторых случаях помогает значительно уменьшить размер дерева и время поиска данных. Если prefix равно NULL (функция не определена) и функция сравнения не определена, то по умолчанию используется лексический метод сравнения. Если prefix равно NULL и функция сравнения определена, то сравнения префиксов не происходит.

lorder

Порядок расположения байтов, заданный для целых чисел, хранящихся в метаданных базы данных. Число должно отражать порядок размещения в виде целого значения; например, порядок «big endian» должен обозначаться числом 4321. Если lorder равно 0 (порядок не определён), то используется значение по умолчанию, принятое на машине.

Если файл уже существует (и не задан флаг O_TRUNC), то значения, определённые в параметрах flags, lorder и psize, игнорируются, приобретая значения, указанные при создании дерева.

Последовательное сканирование дерева производится от меньших ключей к большим.

Место, освобождённое при удалении из дерева пар ключ/данные, в дальнейшем никогда не возвращается, хотя и может использоваться снова. Это значит, что физический размер базы данных может только увеличиваться. Единственное решение — избегать чрезмерного удаления и регулярно создавать новое дерево при помощи полного сканирования старого.

Поиск, вставка и удаление из дерева выполняются за время O lg по основанию N, где основание — средняя скорость заполнения. Довольно часто вставка упорядоченных данных в дерево даёт не столь хорошие результаты, однако, данная реализация изменена так, что работа упорядоченных вставок оказывается наилучшей и во многом более быстрой, чем обычное заполнение.

ОШИБКИ¶

Функции доступа к btree могут завершиться с ошибкой и присвоить errno любое значение из определённых для библиотеки функций dbopen(3).

ДЕФЕКТЫ¶

Поддерживаются значения только с прямым и обратным порядком байт.

СМОТРИТЕ ТАКЖЕ¶

dbopen(3), hash(3), mpool(3), recno(3)

The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138.

Prefix B-trees, Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11-26.

The Art of Computer Programming Vol. 3: Sorting and Searching, D.E. Knuth, 1968, pp 471-480.